///******************** NG.Respate(C)  **********************************
//* 产品名称: Respate 科技
//* 文件名称: Lap_RedBlackTree.c
//* 程序作者: 雷帕特公司(南宫子萍)
//* 程序版本: V1.1														   
//* 编制日期: 2019/1/29
//* 功能描述: avl之红黑树
//* QQ:	2085827949
//**********************************************************************/
#include "Lap_RedBlackTree.h"


#define isTREENULL(ret)  if(tree==NULL) retur ret;

// 插入节点 
static void _insert(redBlackNode* rbtNode,redBlackNode* newNode)
{
	
	if(rbtNode->key > newNode->key)	// 左子树
	{
		if(rbtNode->left ==NULL) {rbtNode->left = newNode;newNode->parent = rbtNode;}
		else _insert(rbtNode->left,newNode);
	}
	else // 右子树
	{
		if(rbtNode->right ==NULL) {rbtNode->right = newNode;newNode->parent = rbtNode;}
		else _insert(rbtNode->right,newNode);
	}
}



// 创建一颗红黑树
rbTree* Lap_rbtCreate(void)
{
	rbTree* tree = (rbTree*)calloc(1,sizeof(rbTree));	// 分配内存
	if(tree==NULL) return NULL;
	return tree;
}




// 插入数据到指定树
int Lap_rbtInsert(rbTree* tree,void* data, int key)
{
	if(tree == NULL || data == NULL) return -1;

	redBlackNode* rbt_node = (redBlackNode*)calloc(1,sizeof(redBlackNode));
	if(rbt_node == NULL) return -1;

	rbt_node->cloor = rbt_RED;			//初始化为 红节点
	rbt_node->ownTree = (rbTree*)tree;	//初始化属主
	rbt_node->data = data;				//挂接数据
	rbt_node->left = NULL;				//左子树初始化为空
	rbt_node->right = NULL;				//右子树初始化为空
	rbt_node->key = key;

	// 上树
	if(tree->root == NULL) tree->root = rbt_node;
	else _insert(tree->root,rbt_node);

	return 0;
}

/*
***********************************************13
**********************************************__|__
*********************************************|321
*********************************************8
*******************************************__|__
*******************************************   
******************************************
*/
char RBT_BUFF[1024*10]={0};
int INDEX=0;
// 遍历树  中序遍历(左->根->右)
int Lap_rbtBL(redBlackNode* root,int d)
{
	int i= 0;
	if(root!=NULL)
	{
		i =Lap_rbtBL(root->left,1);
		for(;i--;INDEX++) RBT_BUFF[INDEX]=' ';

		printf("%d ",root->key);
		Lap_rbtBL(root->right,2);
	}
	return 0;
}

// 指定树删除数据
void* Lap_rbtDelet(redBlackNode* root,int key)
{
	if(root->key == key)
	{
		redBlackNode* temp =NULL;
		(redBlackNode*)(root->parent);
		root->left;
	}
	else if (root->key > key)	Lap_rbtDelet(root->left,key);	//
	else if(root->key < key)	Lap_rbtDelet(root->right,key);	//
	
	return NULL;
}

#if 0
int main(void)
{
	int buff[] = {3,7,4,2,6,10,9,2,11,8};
	rbTree* tree =  Lap_rbtCreate();
	int a=0;

	int i =0;
	for(i=0;i<(sizeof(buff)/sizeof(int));i++)
	{
		Lap_rbtInsert(tree,&a,buff[i]);
	}
	Lap_rbtBL(tree->root,1);
	printf("\r\ni=%d\r\n",sizeof(buff)/sizeof(int));
	return 0;
}
#endif